class Solution(object):
    def getFood(self, grid):
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '*':
                    now = {(i, j)}
                    break
        dist = 0
        while now:
            dist += 1
            next_set = set()
            for x, y in now:
                for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= ux < m and 0 <= uy < n:
                        if grid[ux][uy] == '#':
                            return dist
                        if grid[ux][uy] == 'O':
                            next_set.add((ux, uy))
                            grid[ux][uy] = 'X'
            now = next_set
        return -1
